1. Technical Field
The invention relates to computer compilers. More particularly, the invention relates to a method and apparatus for optimizing computer procedures.
2. Description of the Prior Art
In a procedure-based computer programming language, a procedure is a series of instructions implementing a particular action. When invoked, a procedure typically initiates the building of a construct known as a stack frame. A stack frame stores local variables and other invocation-specific information, such as a return location.
A procedure can call upon one or more other procedures, known as sub-routines, to be executed. Such a procedure is known as a non-terminal procedure. A stack frame is always generated for a non-terminal procedure.
In some cases, the stack frame serves only to maintain the call/return chain. The call/return chain is the designation for the flow of control among the procedures of a program. Procedure calls can be nested as desired in the program. For example, a first procedure may call a second procedure, which builds its own stack frame. The stack may grow in this manner until some procedure completes execution and returns to its caller.
FIG. 1 is a diagram of code showing a procedure call, according to the prior art. A routine "Main" 10 is initially called. This routine builds a stack frame 12. Main, in turn, calls "Procedure 1" 14. The Procedure 1 stack frame 16 includes local variables for the procedure, and invocation-specific information, including the return address 18 to the Main routine. After Procedure 1 executes, this return address directs the program to return to the point directly after the call to Procedure 1 (statement 20).
FIG. 2 is a stack layout diagram, according to the prior art. In the diagram, the stack 24 includes the stack frames 12, 16 for Main and for Procedure 1, respectively. The stack frame for Main stores the local variables 20 and other invocation-specific information for the Main routine. The stack frame 16 built for Procedure 1 stores not only the Procedure 1 local variables 22, but also a pointer to the address in Main to which the program returns when Procedure 1 completes.
When Procedure 1 finishes, it deconstructs its stack frame 16. The stack pointer is moved back to the starting point of the stack frame and control is returned to the address in Main 18 that is saved in the Procedure 1 stack frame 16. This address is immediately after the Call Procedure 1 instruction.
An optimization can be performed on procedures known as "Leaf" procedures. A leaf procedure does not call any other procedures. FIG. 3 is a diagram of a call tree, according to the prior art. In the figure, Main calls Procedure 1 (14), which calls "Procedure 2" 26. Procedure 2 calls "Procedures 3, 4, and 5," 28, 30, 32 which each return to Procedure 2. Main is located at the root of the tree, and Procedures 3,4, and 5 are leaves, because these procedures return and do not call upon other procedures.
Certain leaf procedures do not require the building of a stack frame. For example, in most Reduced Instruction Set Computer (RISC) architectures, when Main calls Procedure 1, it passes the return address in a register. Thus, there is a register devoted specifically to storing the return address from the caller. Runtime conventions specify the register in which the return pointer is to be stored. This register is called the linkage register. If Procedure 1 doesn't need to use this register for other purposes, it can simply hold onto that address in the linkage register for use when Procedure 1 returns.
FIG. 4 is a diagram showing an optimized leaf procedure, according to the prior art. If Procedure 1 (36) has enough registers to store all of its local variables and does not make any calls, it may have no need to build a stack frame. This type of procedure is called a simple procedure. A first optimization that can be performed on a simple leaf procedure is not to build a stack frame. Main 34 stores the return pointer 38 in the linkage register 40, and a simple return is performed after execution of Procedure 1.
Another type of optimization is performed on a recursive procedure. A recursive procedure calls itself. FIG. 5 is a diagram showing a recursive procedure, according to the prior art. In the figure, the code 42 for Procedure 1 includes a call 44 for Procedure 1. A stack frame 46 is built for the first invocation of Procedure 1. When Procedure 1 calls itself, it builds another Procedure 1 stack frame 48.
Each invocation of Procedure 1 results in the building of another, nested Procedure 1 stack frame 50. The call to itself is typically nested in some conditional expression 52, such as "if n=0, call myself." When the condition "n.noteq.0" is reached, the recursion finishes, and the Procedure 1 stack frames sequentially return and deconstruct.
A call occurring immediately before a return instruction is known as a "tail call" 56. A second optimization is known for a tail call in a recursive procedure. In such case, a procedure can use the previous invocation's stack frame.
FIG. 6 is a diagram showing tail recursion elimination, according to the prior art. In the figure, a stack frame 60 is built on the first call 62 of Procedure 1. If the next call 64 of Procedure 1 is a tail call, stack frame 60 is re-used. This continues for each subsequent tail call 66 of the recursive procedure. This can result in a substantial savings in memory, and in the time required for frame construction and deconstruction.
The tail recursion elimination is accomplished by performing a code transformation. While this code transformation is typically done on the machine code, it can also be done on the source code, as is shown in FIG. 7. In the figure, the code 72 for Procedure 1 70 includes a call to itself 74 and a return instruction 76.
The only reason to construct a new stack frame in such a recursive tail call is for storing the return address. In tail recursion elimination, the call and return instructions are transformed to a "goto Procedure 1" 78 instruction. Because the previous invocation includes both the recursive call and a return instruction to be executed at the completion of the procedure, the recursive call is thereby turned into a loop. Subsequent invocations of Procedure 1 do not return, so the new stack frames can be eliminated.
However, the prior art optimization techniques have limited application. The leaf optimization eliminates the stack frames of simple procedures that do not call any other procedures. Tail recursion elimination is performed only on procedures having recursive tail calls. Because a procedure having a recursive tail call is not a leaf procedure, the leaf optimization technique cannot also be performed. Furthermore, the prior art techniques do not significantly improve performance for certain "virtual" procedures in some object-oriented programming languages, such as C++.
It would therefore be an advantage to provide a general method and apparatus for stack frame elimination for simple procedures with tail calls. It would be a further advantage if such method and apparatus also improved performance in object-oriented programming languages.